1. Field of the Invention
This invention relates to computer networks and, more particularly, to an overlay network comprising a plurality of nodes that are interconnected in a manner that enables message routing and failure recovery to be performed efficiently.
2. Description of the Related Art
Computer networks are important for many different applications. One important type of networking is referred to as peer-to-peer or P2P networking. As used herein, a peer-to-peer network is generally used to describe a decentralized network of peer nodes where each node may have similar capabilities and/or responsibilities. Participating peer nodes in a P2P network may communicate directly with each other. Work may be done and information may be shared through interaction among the peers. In addition, in a P2P network, a given peer node may be equally capable of serving as either a client or a server for another peer node.
A peer-to-peer network may be created to fulfill some specific need, or it may be created as a general-purpose network. Some P2P networks are created to deliver one type of service and thus typically run one application. For example, Napster was created to enable users to share music files. Other P2P networks are intended as general purpose networks which may support a large variety of applications. Any of various kinds of distributed applications may execute on a P2P network. Exemplary peer-to-peer applications include file sharing, messaging applications, distributed data storage, distributed processing, etc.
In a typical P2P network, peer nodes communicate with each other via links or virtual communication channels built on top of lower level network connections, such as local area network (LAN) or wide area network (WAN) connections. The set of nodes interconnected by these links is also referred to herein as an overlay network. Any given node in the P2P network may have links to only a small number of nodes relative to the total number of nodes in the system. For example, in a system with 1000 nodes, perhaps each node may have links to only 10 other nodes.
Nodes may send messages to other nodes via the links. For example, various nodes may store routing information that indicates which links to traverse to send messages to particular destinations. The manner in which the nodes are interconnected with links may affect efficiency of the system. Thus, it is desirable to establish the links in such a way that the system is able to operate efficiently. In particular, in many applications it is desirable to establish the links in such a way that the system is able to efficiently route messages and efficiently recover from network failures.